package gold.digger;


import javafx.util.Pair;


/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LCJZOF36 {
    public long startExecuteTime = System.currentTimeMillis();

    class Node {
        public int val;
        public Node left;
        public Node right;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right) {
            val = _val;
            left = _left;
            right = _right;
        }
    }

    class Solution {
        public Node treeToDoublyList(Node root) {
            Pair<Node, Node> tree = midTravelRecur(root);
            if (null == tree) return null;
            tree.getKey().left = tree.getValue();
            tree.getValue().right = tree.getKey();
            return tree.getKey();
        }

        public Pair<Node, Node> midTravelRecur(Node root) {
            if (null == root) return null;
            Pair<Node, Node> prePart = midTravelRecur(root.left);
            Pair<Node, Node> afterPart = midTravelRecur(root.right);
            if (null != prePart) prePart.getValue().right = root;
            root.left = null == prePart ? null : prePart.getValue();
            if (null != afterPart) afterPart.getKey().left = root;
            root.right = null == afterPart ? null : afterPart.getKey();
            return new Pair<>(null == prePart ? root : prePart.getKey(), null == afterPart ? root : afterPart.getValue());
        }
    }

    class SolutionOther {
        Node pre, head;

        public Node treeToDoublyList(Node root) {
            if (root == null) return null;
            dfs(root);
            head.left = pre;
            pre.right = head;
            return head;
        }

        void dfs(Node cur) {
            if (cur == null) return;
            dfs(cur.left);
            if (pre != null) pre.right = cur;
            else head = cur;
            cur.left = pre;
            pre = cur;
            dfs(cur.right);
        }
    }


    public void run() {
        Node n4 = new Node(4);
        Node n2 = new Node(2);
        Node n5 = new Node(5);
        Node n1 = new Node(1);
        Node n3 = new Node(3);

        n4.left = n2;
        n4.right = n5;
        n2.left = n1;
        n2.right = n3;

        Node mine = new Solution().treeToDoublyList(n4);


        Node n44 = new Node(4);
        Node n22 = new Node(2);
        Node n55 = new Node(5);
        Node n11 = new Node(1);
        Node n33 = new Node(3);

        n44.left = n22;
        n44.right = n55;
        n22.left = n11;
        n22.right = n33;

        Node other = new SolutionOther().treeToDoublyList(n44);

        System.out.println(mine);
        System.out.println(other);
    }

    public static void main(String[] args) throws Exception {
        LCJZOF36 an = new LCJZOF36();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
